//解法2：动态规划
//时间复杂度：O（N）
//空间复杂度O(1)
#include<iostream>
using namespace std;
class Solution
{
public:
	int Fibonacci(int n)
	{
		//创建一个数组，保存中间状态的解
		int* F = new int[n + 1];
		//状态初始化 F[0]   F[1]
		F[0] = 0;
		F[1] = 1;
		//状态转移方程：F[i]=F[i-1]+F[i-2];
		for (int i = 2; i <= n; i++)
		{
			F[i] = F[i - 1] + F[i - 2];
		}
		val= F[n];
		return val;
	}
	void Print()const
	{
		cout << val << endl;
	}
private:
	size_t val;
};
int main()
{
	Solution fib;
	fib.Fibonacci(45);
	fib.Print();
	return 0;
}
